{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 线性数据结构\n",
    "\n",
    "## 栈\n",
    "\n",
    "栈是一个线性的有序集合，其中添加移除新项总发生在同一端。这一端通常称为“顶部”。\n",
    "\n",
    "与顶部对应的端称为“底部”。\n",
    "\n",
    "最近添加的项是最先会被移除的。这种排序原则有时被称为LIFO(Last In First Out)，后进先出。\n",
    "\n",
    "它基于在集合内的时间长度做排序。较新的项靠近顶部，较旧的项靠近底部。\n",
    "\n",
    "栈的底部很重要，因为在栈中靠近底部的项是存储时间最长的。\n",
    "\n",
    "栈的例子很常见\n",
    "\n",
    "- 几乎所有的自助餐厅都有一堆托盘或盘子，你从顶部拿一个，就会有一个新的托盘给下一个客人\n",
    "- 想象桌上有一堆书, 只有顶部的那本书封面可见，要看到其他书的封面，只有先移除他们上面的书。\n",
    "\n",
    "![3.3.什么是栈](figures/3.3.stack.png)\n",
    "\n",
    "下图展示了另一个栈，包含了很多 Python 对象。\n",
    "\n",
    "![3.3.什么是栈.primitive](figures/3.3.什么是栈.primitive.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "栈在计算机中非常有用，我们先来看看栈的特点。\n",
    "\n",
    "假设从一个干净的桌面开始，现在把书一本本叠起来，你在构造一个栈。考虑下移除一本书会发生什么。移除的顺序跟刚刚被放置的顺序相反。\n",
    "\n",
    "栈之所以重要是因为它能反转项的顺序，实现了插入跟删除顺序相反。\n",
    "\n",
    "下图展示了 Python 数据对象创建和删除的过程，注意观察他们的顺序。\n",
    "\n",
    "![3.3.什么是栈.simplereversa](figures/3.3.什么是栈.simplereversal.png)\n",
    "\n",
    "想想这种反转的属性，你可以想到使用计算机的时候所碰到的例子。\n",
    "\n",
    "- 每个 web 浏览器都有一个返回按钮。当你浏览网页时，这些网页被放置在一个栈中（实际是网页的网址）。你现在查看的网页在顶部，你第一个查看的网页在底部。如果按‘返回’按钮，将按相反的顺序浏览刚才的页面。\n",
    "\n",
    "- Word的修改也是一个堆栈，“Ctrl-Z”是一个神器。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 栈的抽象数据类型\n",
    "\n",
    "栈的抽象数据类型由以下结构和操作定义。如上所述，栈被构造为项的有序集合，其中项被添加和从末端移除的位置称为“顶部”。栈是有序的 LIFO 。\n",
    "\n",
    "栈操作如下。\n",
    "\n",
    "- Stack() 创建一个空的新栈。 它不需要参数，并返回一个空栈。\n",
    "- push(item) 将一个新项添加到栈的顶部。它需要 item 做参数并不返回任何内容。\n",
    "- pop() 从栈中删除顶部项。它不需要输入参数，并返回一个item ，栈被修改。\n",
    "- peek() 从栈返回顶部项，但不会删除它。不需要输入参数，不修改栈。\n",
    "- isEmpty() 测试栈是否为空。不需要参数，并返回布尔值。\n",
    "- size() 返回栈中的 item 数量。不需要参数，并返回一个整数。\n",
    "\n",
    "例如，s是已经创建的空栈，下表展示了栈操作序列的结果。栈中，顶部项列在最右边。\n",
    "\n",
    "![3.4.栈的抽象数据类型.table1](figures/3.4.栈的抽象数据类型.table1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python实现栈\n",
    "现在我们已经将栈清楚地定义了抽象数据类型，我们将把注意力转向使用 Python 实现栈。回想一下，当我们给抽象数据类型一个物理实现时，我们将实现称为数据结构。\n",
    "\n",
    "与任何面向对象编程语言一样，在Python中抽象数据类型的选择的实现是创建一个新类。栈操作实现为类的方法。此外，为了实现作为元素集合的栈，使用由 Python 提供的原语集合的能力是有意义的。 我们将使用列表作为底层实现。\n",
    "\n",
    "回想一下，Python 中的列表类提供了有序集合机制和一组方法。例如，如果我们有列表 [2,5,3,6,7,4]，我们只需要确定列表的哪一端将被认为是栈的顶部。一旦确定，可以使用诸如 append 和 pop 的列表方法来实现操作。\n",
    "\n",
    "以下栈实现程序，假定列表的结尾将保存栈的顶部元素。随着栈增长（push操作），新项将被添加到列表的末尾。 pop也操作列表末尾的元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "        print(\"Create a new stack!\")\n",
    "\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "\n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "\n",
    "    def pop(self):\n",
    "        return self.items.pop()\n",
    "\n",
    "    def peek(self):\n",
    "        return self.items[len(self.items)-1]\n",
    "\n",
    "    def size(self):\n",
    "        return len(self.items)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "记住上面的代码只定义了栈的类，我们需要创建一个栈，然后使用它。 \n",
    "\n",
    "下面的代码展示了我们通过实例化 Stack 类执行 Table 1中的操作。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Create a new stack!\n",
      "True\n",
      "dog\n",
      "3\n",
      "False\n",
      "8.4\n",
      "True\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "s=Stack()\n",
    "print(s.isEmpty())\n",
    "s.push(4)\n",
    "s.push('dog')\n",
    "print(s.peek())\n",
    "s.push(True)\n",
    "print(s.size())\n",
    "print(s.isEmpty())\n",
    "s.push(8.4)\n",
    "print(s.pop())\n",
    "print(s.pop())\n",
    "print(s.size())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 栈的应用一：简单括号匹配\n",
    "我们现在把注意力转向使用栈解决真正的计算机问题。\n",
    "\n",
    "\n",
    "下面的代码是Lisp语言求平方的函数，这段代码定义了一个名为 square 的函数，它将返回参数的 n 的平方。 \n",
    "\n",
    "\n",
    "*Lisp 使用大量的圆括号是臭名昭著的*。\n",
    "\n",
    "```lisp\n",
    "(defun square(n)\n",
    "     (* n n))\n",
    "```\n",
    "\n",
    "\n",
    "在这两个例子中，括号必须以匹配的方式出现。括号匹配意味着每个开始符号具有相应的结束符号，并且括号能被正确嵌套。考虑下面正确匹配的括号字符串：\n",
    "\n",
    "```python\n",
    "(()()()())\n",
    "\n",
    "(((())))\n",
    "\n",
    "(()((())()))\n",
    "```\n",
    "对比那些不匹配的括号：\n",
    "\n",
    "```python\n",
    "((((((())\n",
    "\n",
    "()))\n",
    "\n",
    "(()()(()\n",
    "```\n",
    "\n",
    "\n",
    "区分括号是否匹配的能力是识别很多编程语言结构的重要部分。具有挑战的是如何编写一个算法，能够从左到右读取一串符号，并决定括号是否平衡。\n",
    "\n",
    "为了解决这个问题，我们需要以下的重要观察结果。\n",
    "- 从左到右处理符号时，最近开始符号必须与下一个关闭符号相匹配。\n",
    "- 处理的第一个开始符号必须等待直到其匹配最后一个符号。结束符号以相反的顺序匹配开始符号。他们从内到外匹配。\n",
    "\n",
    "![3.6.简单括号匹配.simpleparcheck](figures/3.6.%E7%AE%80%E5%8D%95%E6%8B%AC%E5%8F%B7%E5%8C%B9%E9%85%8D.simpleparcheck.png)\n",
    "\n",
    "\n",
    "栈就是解决这个问题很恰当的数据结构，算法是很直接的。\n",
    "- 从空栈开始，从左到右处理括号字符串。\n",
    "- 如果一个符号是一个开始符号，将其作为一个信号，对应的结束符号稍后会出现。\n",
    "- 如果符号是结束符号，则弹出栈，只要弹出栈的开始符号可以匹配结束符号，则括号保持匹配状态。**如果任何时候栈上没有出现符合开始符号的结束符号，则字符串不匹配**。\n",
    "- 当所有符号都被处理后，栈应该是空的，如果非空，也表明括号是不匹配的。\n",
    "\n",
    "实现此算法的 Python 代码如下所示。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def parChecker(symbolString):\n",
    "    s = Stack()\n",
    "    balanced = True\n",
    "    index = 0\n",
    "    while index < len(symbolString) and balanced:\n",
    "        symbol = symbolString[index]\n",
    "        if symbol == \"(\":\n",
    "            s.push(symbol)\n",
    "        else:\n",
    "            if s.isEmpty():\n",
    "                balanced = False\n",
    "            else:\n",
    "                s.pop()\n",
    "        index = index + 1\n",
    "\n",
    "    if balanced and s.isEmpty():\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "print(parChecker('((()()(()))))'))\n",
    "print(parChecker('(()'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 栈的应用二：符号匹配\n",
    "上面显示的匹配括号问题是许多编程语言都会出现的一般情况的特定情况。匹配和嵌套不同种类的开始和结束符号的情况经常发生。例如，在 Python 中，方括号 `[` 和 `]` 用于列表，花括号 `{` 和 `}` 用于字典。括号 `(` 和 `)` 用于元祖和算术表达式。只要每个符号都能保持自己的开始和结束关系，就可以混合符号。\n",
    "\n",
    "下面的字符串被恰当的匹配了，因为不仅每个开始符号都有对应的结束符号，而且符号的类型也匹配。\n",
    "```python\n",
    "{ { ( [ ] [ ] ) } ( ) }\n",
    "[ [ { { ( ( ) ) } } ] ]\n",
    "[ ] [ ] [ ] ( ) { }\n",
    "```\n",
    "\n",
    "相反下面的字符串没法匹配：\n",
    "```python\n",
    "( [ ) ]\n",
    "( ( ( ) ] ) )\n",
    "[ { ( ) ]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上节的简单括号检查程序可以轻松的扩展处理这些新类型的符号。回想一下，每个开始符号被简单的压入栈中，等待匹配的结束符号出现。当出现结束符号时，唯一的区别是我们必须检查确保它正确匹配栈顶部开始符号的类型。如果两个符号不匹配，则字符串不匹配。如果整个字符串都被处理完并且没有什么留在栈中，则字符串匹配。\n",
    "\n",
    "Python 程序见下面的代码。唯一的变化是 16 行，我们称之为辅助函数匹配。必须检查栈中每个删除的符号，以查看它是否与当前结束符号匹配。如果不匹配，则布尔变量 balanced 被设置为 False。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def parChecker(symbolString):\n",
    "    s = Stack()\n",
    "    balanced = True\n",
    "    index = 0\n",
    "    while index < len(symbolString) and balanced:\n",
    "        symbol = symbolString[index]\n",
    "        if symbol in \"([{\":\n",
    "            s.push(symbol)\n",
    "        else:\n",
    "            if s.isEmpty():\n",
    "                balanced = False\n",
    "            else:\n",
    "                top = s.pop()\n",
    "                if not matches(top, symbol):\n",
    "                       balanced = False\n",
    "        index = index + 1\n",
    "    if balanced and s.isEmpty():\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def matches(open, close):\n",
    "    opens = \"([{\"\n",
    "    closers = \")]}\"\n",
    "    return opens.index(open) == closers.index(close)\n",
    "\n",
    "\n",
    "print(parChecker('{{([][])}()}'))\n",
    "print(parChecker('[{()]'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "这两个例子表明，栈是计算机语言结构处理非常重要的数据结构。几乎你能想到的任何嵌套符号必须按照平衡匹配的顺序。\n",
    "\n",
    "栈还有其他重要的用途，我们将在接下来的部分讨论。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 栈的应用三：十进制转换成二进制\n",
    "\n",
    "在你学习计算机的过程中，你可能已经接触了二进制。二进制在计算机科学中是很重要的，因为存储在计算机内的所有值都是以 0 和 1 存储的。如果没有能力在二进制数和普通字符串之间转换，我们与计算机之间的交互非常棘手。\n",
    "\n",
    "整数值是常见的数据项。他们一直用于计算机程序和计算。我们在数学课上学习它们，当然最后用十进制或者基数 10 来表示它们。十进制 0d233以及对应的二进制表示 0b11101001分别解释为\n",
    "\n",
    ">B: binary  二进制的\n",
    "Q: quaternary 四进制的\n",
    "D: decimal 十进制的\n",
    "H: hexadecimal 十六进制的\n",
    "O: octal 八进制的.\n",
    "\n",
    "$$233 = 2*10^2+3*10^1+3*10^0$$\n",
    "$$233 = 1*2^7+1*2^6+1*2^5+0*2^4+1*2^3+0*2^2+0*2^1+1*2^0$$\n",
    "\n",
    "但是我们如何能够容易地将整数值转换为二进制呢？答案是 “除 2”算法，它用栈来跟踪二进制结果的数字。\n",
    "\n",
    "“除 2” 算法假定我们从大于 0 的整数开始。不断迭代的将十进制除以 2，并跟踪余数。第一个除以 2 的余数说明了这个值是偶数还是奇数。偶数有 0 的余数，记为 0。奇数有余数 1，记为 1.我们将得到的二进制构建为数字序列，第一个余数实际上是序列中的最后一个数字。见下图, 我们再次看到了反转的属性，表示栈可能是解决这个问题的数据结构。\n",
    "\n",
    "![3.8.十进制转换成二进制.figure5](figures/3.8.%E5%8D%81%E8%BF%9B%E5%88%B6%E8%BD%AC%E6%8D%A2%E6%88%90%E4%BA%8C%E8%BF%9B%E5%88%B6.figure5.png)\n",
    "\n",
    "下面的 Python 代码实现了 “除 2” 算法，函数 divideBy2 传入了一个十进制的参数，并重复除以 2。第 7 行使用内置的模运算符 % 来提取余数，第 8 行将余数压到栈上。当除到 0 后，11-13 行构造了一个二进制字符串。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def divideBy2(decNumber):\n",
    "    remstack = Stack()\n",
    "\n",
    "    while decNumber > 0:\n",
    "        rem = decNumber % 2\n",
    "        remstack.push(rem)\n",
    "        decNumber = decNumber // 2\n",
    "\n",
    "    binString = \"\"\n",
    "    while not remstack.isEmpty():\n",
    "        binString = binString + str(remstack.pop())\n",
    "\n",
    "    return binString\n",
    "\n",
    "print(divideBy2(42))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "这个用于二进制转换的算法可以很容易的扩展以执行任何基数的转换。在计算机科学中，通常会使用很多不同的编码。其中最常见的是二级制，八进制和十六进制。\n",
    "\n",
    "十进制 233 和它对应的八进制和十六进制 0o351, 0xE9\n",
    "\n",
    "$$233 = 3*8^2 + 5*8^1 + 1*8^0$$\n",
    "$$233 = E*16^1 + 9*16^0$$\n",
    "\n",
    "可以修改 divideBy2 函数，使它不仅能接受十进制参数，还能接受预期转换的基数。‘除 2’ 的概念被简单的替换成更通用的 ‘除基数’。\n",
    "\n",
    "下面代码展示的是一个名为 baseConverter 函数。采用十进制数和 2 到 16 之间的任何基数作为参数。余数部分仍然入栈，直到被转换的值为 0。我们创建一组数字，用来表示超过 9 的余数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11001\n",
      "19\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def baseConverter(decNumber,base):\n",
    "    digits = \"0123456789ABCDEFG\"\n",
    "\n",
    "    remstack = Stack()\n",
    "\n",
    "    while decNumber > 0:\n",
    "        rem = decNumber % base\n",
    "        remstack.push(rem)\n",
    "        decNumber = decNumber // base\n",
    "\n",
    "    newString = \"\"\n",
    "    while not remstack.isEmpty():\n",
    "        newString = newString + digits[remstack.pop()]\n",
    "\n",
    "    return newString\n",
    "\n",
    "print(baseConverter(25, 2))\n",
    "print(baseConverter(25, 17))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.28 µs ± 41.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit baseConverter(25, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8E3\n"
     ]
    }
   ],
   "source": [
    "print(baseConverter(2553, 17))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 栈的应用四：中缀、前缀和后缀表达式\n",
    "\n",
    "当你编写一个算术表达式如 $B*C$ 时，表达式的形式使你能够正确理解它。在这种情况下，你知道 B 乘以 C, 因为乘法运算符 $*$ 出现在表达式中。这种类型的符号称为中缀，因为运算符在它处理的两个操作数之间。\n",
    "\n",
    "看另一个中缀表达示例，$A+B*C$，运算符 $+$ 和 $*$ 仍然出现在操作数之间。这里面有个问题是，他们分别作用于哪个运算数上？$+$ 作用于 A 和 B , 还是 $*$ 先作用于 B 和 C？表达式似乎有点模糊。\n",
    "\n",
    "事实上，你已经读写过这些类型的表达式很长一段时间，所以它们对你不会导致什么问题。这是因为你知道运算符 $+$和$*$。\n",
    "\n",
    "每个运算符都有一个优先级。优先级较高的运算符在优先级较低的运算符之前使用。唯一改变顺序的是括号的存在。算术运算符的优先顺序是将乘法和除法置于加法和减法之上。如果出现具有相等优先级的两个运算符，则使用从左到右的顺序排序或关联。\n",
    "\n",
    "我们使用运算符优先级来解释下表达式 `A+B*C`。B 和 C 首先相乘，然后将 A 与该结果相加。`(A+B)*C` 将强制在乘法之前执行 A 和 B 的加法。在表达式 `A+B+C` 中，最左边的 + 首先使用。\n",
    "\n",
    "虽然这一切对你来说都很明显。但请记住，计算机需要准确知道要执行的操作符和顺序。一种保证不会对操作顺序产生混淆的表达式的方法是创建一个称为**完全括号表达式**的形式。这种类型的表达式对每个运算符都使用一对括号。\n",
    "\n",
    "括号没有歧义的指示操作的顺序，也没有必要记住任何优先规则。\n",
    "\n",
    "表达式 `A+B*C+D` 可以重写为 `((A + (B * C)) + D)` ，表明先乘法，然后是左边的加法，` A + B + C + D` 可以写为 `(((A + B) + C) + D)`，因为加法操作从左向右相关联。\n",
    "\n",
    "有两种非常重要的表达式格式，你可能一开始不会很习惯。\n",
    "\n",
    "中缀表达式 `A+B`, 如果我们移动两个操作数之间的运算符会发生什么？结果表达式变成 `+ A B`。同样，我们也可以将运算符移动到结尾，得到 `A B +` ，这样看起来有点奇怪。\n",
    "\n",
    "改变操作符的位置得到了两种新的表达式格式，**前缀和后缀**。\n",
    "\n",
    "**前缀表达式符号要求所有运算符在它们处理的两个操作数之前。另一个方面，后缀要求其操作符在相应的操作数之后**。\n",
    "\n",
    "看下更多的例子 (见下表)\n",
    "`A+B*C` 将在前缀中写为 `+ A * B C` 。乘法运算符紧接在操作数 B 和 C 之前，表示 `*` 优先于 `+`。然后加法运算符出现在 A 和乘法的结果之前。\n",
    "\n",
    "在后缀中，表达式将是 `A B C * +`，再次，操作的顺序被保留，因为 `*` 紧接在 B 和 C 之后出现，表示 `*` 具有高优先级，`+` 优先级低。虽然操作符在它们各自的操作数前后移动，但是顺序相对于彼此保持完全相同。\n",
    " \n",
    "![3.9.中缀后缀和后缀表达式.table2](figures/3.9.%E4%B8%AD%E7%BC%80%E5%90%8E%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F.table2.png)\n",
    "\n",
    "现在考虑中缀表达式 `(A + B) * C`，回想下，在这种情况下，中缀需要括号在乘法之前强制执行加法。然而，当 A+B 写到前缀中时，加法运算符简单的移动到操作数 `+ A B` 之前。这个操作的结果成为乘法的第一个操作数。乘法运算符移动到整个表达式的前面，得出 `* + A B C`，同样，在后缀 `A B +`中，强制先加法。可以直接对该结果和剩余的操作数 C 相乘。然后，得出后缀表达式为 `A B + C *`。\n",
    "\n",
    "再次考虑这三个表达式(见下表)，括号不见了。为什么在**前缀和后缀的时候不需要括号**了呢？答案是操作符对于他们的**操作数不再模糊，前缀和后缀表达式的操作顺序完全由操作符的顺序决定**。\n",
    "\n",
    "![3.9.中缀后缀和后缀表达式.table3](figures/3.9.%E4%B8%AD%E7%BC%80%E5%90%8E%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F.table3.png)\n",
    "\n",
    "\n",
    "下表展示了一些其他的例子\n",
    "\n",
    "![3.9.中缀后缀和后缀表达式.table4](figures/3.9.%E4%B8%AD%E7%BC%80%E5%90%8E%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F.table4.png)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 中缀表达式转换前缀和后缀\n",
    "到目前为止，我们已经使用特定方法在中缀表达式和等效前缀和后缀表达式符号之间进行转换。正如你可能期望的，有一些算法来执行转换，允许任何复杂表达式转换。\n",
    "\n",
    "我们考虑的第一种技术使用前面讨论的完全括号表达式的概念。回想一下，`A + B * C`可以写成`（A +（B * C））`，以明确标识乘法优先于加法。然而，仔细观察,你可以看到每个括号对还表示操作数对的开始和结束，中间有相应的运算符。\n",
    "\n",
    "看上面的子表达式`（B * C）`中的右括号。 如果我们将乘法符号移动到那个位置，并删除匹配的左括号，得到 `B C * `，我们实际上已经将子表达式转换为后缀符号。 如果加法运算符也被移动到其相应的右括号位置并且匹配的左括号被去除，则将得到完整的后缀表达式（见下图）。\n",
    "\n",
    "![3.9.中缀后缀和后缀表达式.figure6](figures/3.9.%E4%B8%AD%E7%BC%80%E5%90%8E%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F.figure6.png)\n",
    "\n",
    "\n",
    "如果我们不是将符号移动到右括号的位置，我们将它向左移动，我们得到前缀符号（见下图）。圆括号对的位置实际上是包含的运算符的最终位置的线索。\n",
    "![3.9.中缀后缀和后缀表达式.figure7](figures/3.9.%E4%B8%AD%E7%BC%80%E5%90%8E%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F.figure7.png)\n",
    "\n",
    "\n",
    "所以为了转换表达式，无论是对前缀还是后缀符号，先根据操作的顺序把表达式转换成完全括号表达式。然后将包含的运算符移动到左或右括号的位置，具体取决于需要前缀或后缀符号。\n",
    "\n",
    "这里面有个更复杂的例子, `(A + B) * C - (D - E) * (F + G)` ，下图显示了如何转换为后缀和前缀。\n",
    "\n",
    "![3.9.中缀后缀和后缀表达式.figure8](figures/3.9.%E4%B8%AD%E7%BC%80%E5%90%8E%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F.figure8.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 中缀转后缀通用法\n",
    "\n",
    "**我们需要开发一个算法来将任何中缀表达式转换为后缀表达式。** \n",
    "\n",
    "为了做到这一点，我们仔细看看转换过程。\n",
    "\n",
    "再次考虑表达式 `A + B * C`。如上所示，`A B C * +`是等价的后缀表达式。 我们已经注意到，操作数 A，B 和 C 保持在它们的相对位置。只有操作符改变位置。再看中缀表达式中的运算符。从左到右出现的第一个运算符为 +。 然而，在后缀表达式中，+ 在结束位置，因为下一个运算符 * 的优先级高于加法。 原始表达式中的运算符的顺序在生成的后缀表达式中相反。\n",
    "\n",
    "当我们处理表达式时，操作符必须保存在某处，因为它们相应的右操作数还没有看到。 此外，这些保存的操作符的顺序可能由于它们的优先级而需要反转。这是在该示例中的加法和乘法的情况，由于加法运算符在乘法运算符之前，并且具有较低的优先级，因此需要在使用乘法运算符之后出现。 **由于这种顺序的反转，考虑使用栈来保存运算符直到用到它们是有意义的。**\n",
    "\n",
    "带括号的`(A + B)* C`的情况会是什么样呢？ 回想一下，`A B + C *`是等价的后缀表达式。从左到右处理此中缀表达式，我们先看到 `+`。 在这种情况下，当我们看到 `*`，` + `已经放置在结果表达式中，由于括号它的优先级高于`*`。 我们现在可以开始看看转换算法如何工作。当我们看到左括号时，我们保存它，表示高优先级的另一个运算符将出现。该操作符需要等到相应的右括号出现以表示其位置（回忆完全括号的算法）。 当右括号出现时，可以从栈中弹出操作符。\n",
    "\n",
    "当我们从左到右扫描中缀表达式时，我们将使用栈来保留运算符。这将提供我们在第一个例子中注意到的反转。 堆栈的顶部将始终是最近保存的运算符。每当我们读取一个新的运算符时，我们需要考虑该运算符如何与已经在栈上的运算符（如果有的话）比较优先级。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "假设中缀表达式是一个由空格分隔的标记字符串。 操作符标记是`*，/，+`和 `-` ，以及左右括号。操作数是单字符 A，B，C 等。 以下步骤将后缀顺序生成一个字符串。\n",
    "\n",
    "1. 创建一个名为 opstack 的空栈以保存运算符。给输出创建一个空列表。\n",
    "2. 通过使用字符串方法拆分将输入的中缀字符串转换为标记列表。\n",
    "3. 从左到右扫描标记列表。\n",
    "    - 如果标记是操作数，将其附加到输出列表的末尾。\n",
    "    - 如果标记是左括号，将其压到 opstack 上。\n",
    "    - 如果标记是右括号，则弹出 opstack，直到删除相应的左括号。将每个运算符附加到输出列表的末尾。\n",
    "    - 如果标记是运算符，`*，/，+`或 `-` ，将其压入 opstack。但是，首先删除已经在 opstack 中具有更高或相等优先级的任何运算符，并将它们加到输出列表中。\n",
    "4. 当输入表达式被完全处理时，检查 opstack。仍然在栈上的任何运算符都可以删除并加到输出列表的末尾。\n",
    "\n",
    "下图展示了对表达式 `A * B + C * D` 的转换算法。注意，第一个 `*` 在看到 `+` 运算符时被删除。另外，当第二个 * 出现时， `+` 保留在栈中，因为乘法优先级高于加法。在中缀表达式的末尾，栈被弹出两次，删除两个运算符，并将 `+` 作为后缀表达式中的最后一个运算符。\n",
    "\n",
    "![3.9.中缀后缀和后缀表达式.figure9](figures/3.9.%E4%B8%AD%E7%BC%80%E5%90%8E%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F.figure9.png)\n",
    "\n",
    "\n",
    "为了在 Python 中编写算法，我们使用一个名为 prec 的字典来保存操作符的优先级。这个字典将每个运算符映射到一个整数，可以与其他运算符的优先级（我们使用整数3，2和1）进行比较。左括号将赋予最低的值。这样，与其进行比较的任何运算符将具有更高的优先级，将被放置在它的顶部。第15行将操作数定义为任何大写字符或数字。完整的转换函数如下。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "def infixToPostfix(infixexpr):\n",
    "    prec = {}\n",
    "    prec[\"*\"] = 3\n",
    "    prec[\"/\"] = 3\n",
    "    prec[\"+\"] = 2\n",
    "    prec[\"-\"] = 2\n",
    "    prec[\"(\"] = 1\n",
    "    opStack = Stack()\n",
    "    postfixList = []\n",
    "    tokenList = infixexpr.split()\n",
    "\n",
    "    for token in tokenList:\n",
    "        if token in \"ABCDEFGHIJKLMNOPQRSTUVWXYZ\" or token in \"0123456789\":\n",
    "            postfixList.append(token)\n",
    "        elif token == '(':\n",
    "            opStack.push(token)\n",
    "        elif token == ')':\n",
    "            topToken = opStack.pop()\n",
    "            while topToken != '(':\n",
    "                postfixList.append(topToken)\n",
    "                topToken = opStack.pop()\n",
    "        else:\n",
    "            while (not opStack.isEmpty()) and \\\n",
    "               (prec[opStack.peek()] >= prec[token]):\n",
    "                  postfixList.append(opStack.pop())\n",
    "            opStack.push(token)\n",
    "\n",
    "    while not opStack.isEmpty():\n",
    "        postfixList.append(opStack.pop())\n",
    "    return \" \".join(postfixList)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "执行结果如下"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'A B * C D * +'"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "infixToPostfix(\"A * B + C * D\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'A B + C * D E - F G + * -'"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "infixToPostfix(\"( A + B ) * C - ( D - E ) * ( F + G )\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'A B + C D + *'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "infixToPostfix(\"( A + B ) * ( C + D )\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'A B + C *'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "infixToPostfix(\"( A + B ) * C\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'A B C * +'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "infixToPostfix(\"A + B * C\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 后缀表达式求值\n",
    "\n",
    "作为最后栈的示例，我们考虑对后缀符号中的表达式求值。\n",
    "\n",
    "针对这种情况，栈再次是我们选择的数据结构。但是，在扫描后缀表达式时，它必须等待操作数，而不像上面的转换算法中的运算符。 解决问题的另一种方法是，每当在输入上看到运算符时，计算两个最近的操作数。\n",
    "\n",
    "要详细的了解这一点，考虑后缀表达式 ` 4 5 6 * +`， 首先遇到操作数 `4` 和 `5`，此时，你还不确定如何处理它们，直到看到下一个符号。将它们放置到栈上，确保它们在下一个操作符出现时可用。\n",
    "\n",
    "在这种情况下，下一个符号是另一个操作数。所以，像先前一样，压入栈中。并检查下一个符号。现在我们看到了操作符 `*`，这意味着需要将两个最近的操作数相乘。通过弹出栈两次，我们可以得到正确的两个操作数，然后执行乘法（这种情况下结果为 30）。\n",
    "\n",
    "我们现在可以通过将其放回栈中来处理此结果，以便它可以表示为表达式后面的运算符的操作数。当处理最后一个操作符时，栈上只有一个值，弹出并返回它作为表达式的结果。下图 展示了整个示例表达式的栈的内容。\n",
    "![3.9.中缀后缀和后缀表达式.figure10](figures/3.9.%E4%B8%AD%E7%BC%80%E5%90%8E%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F.figure10.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下图是个稍微复杂的示例，`7 8 + 3 2 + /` 。在这个例子中有两点需要注意，首先，栈的大小增长收缩，然后再子表达式求值的时候再次增长。第二，除法操作需要处理。回想下，后缀表达式的操作符顺序没变，仅仅改变操作符的位置。当用于除法的操作符从栈中弹出时，它们被反转。由于除法不是交换运算符，换句话说 `15/5`和 `5/15` 不同，因此我们必须保证操作数的顺序不会交换。\n",
    "\n",
    "![3.9.中缀后缀和后缀表达式.figure11](figures/3.9.%E4%B8%AD%E7%BC%80%E5%90%8E%E7%BC%80%E5%92%8C%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F.figure11.png)\n",
    "\n",
    "\n",
    "假设后缀表达式是一个由空格分隔的标记字符串。 运算符为`*，/，+`和 `-` ，操作数假定为单个整数值。 输出将是一个整数结果。\n",
    "\n",
    "1. 创建一个名为 `operandStack` 的空栈。\n",
    "2. 拆分字符串转换为标记列表。\n",
    "3. 从左到右扫描标记列表。\n",
    "    - 如果标记是操作数，将其从字符串转换为整数，并将值压到operandStack。\n",
    "    - 如果标记是运算符`*，/，+`或` - `，它将需要两个操作数。弹出operandStack 两次。 第一个弹出的是第二个操作数，第二个弹出的是第一个操作数。执行算术运算后，将结果压到操作数栈中。\n",
    "4. 当输入的表达式被完全处理后，结果就在栈上，弹出 operandStack 并返回值。\n",
    "\n",
    "用于计算后缀表达式的完整函数如下所示，为了辅助计算，定义了一个函数 doMath, 它将获取两个操作数和运算符，执行相应的计算。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['7', '8', '+', '3', '2', '+', '/']\n",
      "3.0\n"
     ]
    }
   ],
   "source": [
    "from pythonds.basic.stack import Stack\n",
    "\n",
    "\n",
    "def postfixEval(postfixExpr):\n",
    "    operandStack = Stack()\n",
    "    tokenList = postfixExpr.split()\n",
    "    print(tokenList)\n",
    "\n",
    "    for token in tokenList:\n",
    "        if token not in \"+-*/\":\n",
    "            # print(token)\n",
    "            operandStack.push(int(token))\n",
    "        else:\n",
    "            operand2 = operandStack.pop()  # 注意operand2先弹出\n",
    "            operand1 = operandStack.pop()\n",
    "            result = doMath(token, operand1, operand2)\n",
    "            operandStack.push(result)\n",
    "    return operandStack.pop()\n",
    "\n",
    "\n",
    "def doMath(op, op1, op2):\n",
    "    if op == \"*\":\n",
    "        return op1 * op2\n",
    "    elif op == \"/\":\n",
    "        return op1 / op2\n",
    "    elif op == \"+\":\n",
    "        return op1 + op2\n",
    "    else:\n",
    "        return op1 - op2\n",
    "\n",
    "\n",
    "print(postfixEval('7 8 + 3 2 + /'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['12', '14', '16', '8', '9', '6', '4']\n",
      "[12, 14, 16, 8, 9, 6, 4]\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXAAAAD4CAYAAAD1jb0+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO3deXhU9d3+8fcnOxD2BBJIMILsYXXCIhJERBZ3KQG1igvSqnXj1/ax2qfq1da2to9L1aqAuFIFF6wbiLgAIltYE1ZBkAQICftOtu/vD2JrUbZkJiczc7+uq1fIMMy5x+rNN98553PMOYeIiASfCK8DiIhI5ajARUSClApcRCRIqcBFRIKUClxEJEhFVefBEhISXFpaWnUeUkQk6C1evHiHcy7x+MertcDT0tLIzs6uzkOKiAQ9M/v2xx7XFoqISJBSgYuIBCkVuIhIkFKBi4gEKRW4iEiQOmWBm9lEMys0s9zjHr/TzNaa2UozezRwEUVE5Meczgr8JWDw9x8ws/7AFUBn51xH4G/+jyYiIidzygJ3zs0Gdh338G3An51zRyueUxiAbFKDHThayqQF37L3cInXUUTCVmX3wNsAfc1sgZnNMrOMEz3RzMaYWbaZZRcVFVXycFKTzFpXxKDHZ/PA1Fyem7XB6zgiYauyBR4FNAR6Ab8CppiZ/dgTnXPjnHM+55wvMfEHV4JKENlzqJixU5YxauJC4qIj6JJSn7cX51NaVu51NJGwVNkCzwfecccsBMqBBP/Fkprmo5xtXPTYLN5btpU7LzyHj+7uy20XnEPh/qPMWqefrES8UNlZKO8CFwJfmFkbIAbY4bdUUmMU7jvC//4rl49XbqdT8/q8cnNPOjSrB8CA9k1IiI9hSnYeA9o39TipSPg5ZYGb2evABUCCmeUDDwITgYkVpxYWA6Ocbq4ZUpxzvLk4nz98sIqjpeXcN6Qdo88/m6jI//zQFh0ZwVXdmvPi3E0U7T9KYt1YDxOLhJ9TFrhz7poT/NZP/ZxFaoi8XYf4zTs5fLl+Bz3SGvHnYZ1omRj/o8/N8qUyfs5G3l26hVszW1ZzUpHwVq3jZKVmKyt3vDJvE49OX0tkhPH7K9O5rkcLIiJ+9PNpAFo3rUu3Fg2YnJ3H6L5nc4LPskUkAHQpvQCwvnA/w5/7ioffX0XPlo2YcW8m1/c666Tl/Z0RvlTWFx5gad6eakgqIt9RgYe5krJynv7sa4Y++SUbdxzkiRFdefHGDJo1qHXar3FJ52RqRUcyZVFeAJOKyPG0hRLGcvL38qu3lrOmYD+Xdk7mocs7khB/5h9E1o2L5pLOyby/fCv/e2kH6sTqXyuR6qAVeBg6UlLGn6at5opnvmTXwWLGXX8uT1/bvVLl/Z0sXyoHi8v4KGebH5OKyMloqRRmFnyzk/veyWHjjoOMzEjlN0PbU79WdJVfNyOtIS0T6jAlO4/hvlQ/JBWRU9EKPEzsP1LCb9/NYcS4+ZSVOyaN7smfh3X2S3kDmBnDfaks2rSbb4oO+OU1ReTkVOBh4PM1hQx6fDb/XLCZ0eefzfR7+tLnHP9PPhjWvTmREcaU7Hy/v7aI/JAKPITtOljMvZOXcdNLi6gTG8Xbt53Hby/tQO2YwOycNakXR/+2iby9RAOuRKqD9sBDkHOOD1Zs46H3VrL3cAl3D2jN7f1bERsVGfBjD/elMnN1IV+sLeKiDpqPIhJIKvAQs33fER6YmsvM1dvpnFKfSbf2pF1SvWo7/oXt/jPgSgUuElgq8BDhnGPyojz++NFqikvLeWBoe27qk/Zfw6eqQ3RkBFd3T2Hilxs14EokwLQHHgI27zzEdRMWcN87OXRsVo+P78nk1syW1V7e38nypVBa7pi6VB9migSSVuBBrKzc8eLcjfxtxlqiIyJ45KpOjMxIPa35JYF0TpO6dG/RgMmL8ri1b0sNuBIJEK3Ag9S67fsZ9uxX/OHD1fRplcCMsZlc2/PkkwOr04iMVDYUHWTJZg24EgkUFXiQKS4t58mZX3PJ3+ewedchnhzZlQmjfCTXP/3hU9Xhks7NqB2jAVcigaQtlCCyPG8Pv35rBWu37+eKrs343aUdaFyF+SWBFB8bxSWdkvlgxVZ+d5kGXIkEglbgQeBwcRl//HAVV/1jLnsPlzDhBh9PjuxWY8v7O1kZxwZcfagBVyIBoWVRDTdvw07ue2cF3+48xLU9W3DfkHbUi/PP/JJA853VkJaJdZiyKI8sDbgS8TutwGuofUdK+M07OVwzfj4Ar9/ai0eu6hQ05Q3HBlxl+VLJ/nY3GzTgSsTvVOA10Kert3PxY7OZvGgzYzJbMv3uTHq3aux1rEq5+t8DrvRhpoi/qcBrkJ0HjnLX60u55eVsGtSOZurtfbh/aHtqxQR+hkmgNKkbR/+2TXh78RZKNOBKxK+0B14DOOd4b/lWHnpvJQeOlnLvRW247YJWxESFxt+vWb4UZq7ezhdrixio+SgifqMC99i2vYf57dRcPl1TSNfUBjz6k860aVrX61h+1b9dExLiY5mSnacCF/GjUy7xzGyimRWaWe6P/N4vzcyZmf/vDhDiyssdkxZ8y8DHZjN3ww5+e0l73r7tvJArbzg24GpY9+Z8tqaQwv1HvI4jEjJO52f0l4DBxz9oZqnAQGCznzOFvE07DnLthPk8MDWXzin1mXFPP0b3bUlkDbkMPhCG+1IpK3dMXbLF6ygiIeOUBe6cmw3s+pHfehz4NeD8HSpUlZaVM272BgY9MZuVW/fxl2GdmDS6Jy0a1/Y6WsCd0ySec89qyOTsPJzTvzIi/lCpT8nM7HJgi3Nu+Wk8d4yZZZtZdlFRUWUOFxLWFOxj2LNf8chHa+jbOpGZY/sxIqNFWE3qG+FL5ZuigyzZvNvrKCIh4YwL3MxqAw8Avzud5zvnxjnnfM45X2Ji4pkeLugdLS3jsU/WcenfvyR/92GevrYb4284l6b14ryOVu2Gdk6mdkwkkzXgSsQvKrMCbwWcDSw3s01ACrDEzJL8GSwULNm8m0v//iV///RrLuvSjJlj+3Fp52Zhter+vvjYKC7tnMwHK7Zx8Gip13FEgt4ZF7hzLsc518Q5l+acSwPyge7OuQK/pwtSh4pL+f0Hqxj27FccOFrKizdm8PiIrjSsE+N1NM+NyEjlUHEZH67QgCuRqjqd0whfB+YBbc0s38xuCXys4DV3/Q4GPTGbF77cyHU9WzDj3kz6t2vidawao3uLYwOuJuvSepEqO+WFPM65a07x+2l+SxPE9h4u4U8freaNRXmcnVCHyWN60bNlcM4vCSQzY4QvlT9NW8P6wgOc0yTe60giQSs0rtX22IyVBQx8bBZvLs7n5/1aMe3uvirvk7iqYsDVm1qFi1SJCrwKivYf5Y5/LmHMq4tpHB/Lu7f34b4h7YiLDt7hU9WhSd04LmzXhLeXaMCVSFVoFkolOOd4d9kWHn5/FYeOlvHLi9vws36tiI7U34enK8uXyiertvP5mkIu7qgTmEQqQwV+hrbsOcwDU3P4Ym0R3VscGz51TpPQm18SaP3bJpJYN5Yp2fkqcJFKUoGfpvJyx6SFm/nzR6spd/DgZR24oXdaSM8vCaSoyAiu7t6cCXM2UrjvCE3C8MImkarSz/yn4ZuiA4wcN5//fTeXbi0aMuPeTG7qc7bKu4qyKgZcvbNUA65EKkMr8JMoLStn/JyNPD5zHXFRETz6k84MPzclbK+k9LdWifH4zmrIlEV5/Cyzpf65ipwhrcBPYNXWfVz5j7n8Zfoa+rc9Nnwqy5eqkvGzrIxUvtlxkMXfasCVyJlSgR/nSEkZf/t4LZc//SUFe4/y7HXdef56n/ZoA+SSTsnU0YArkUpRgX/P4m93ccnf5/D05+u5omtzZo7NZEinZK9jhbQ6sVFc2rkZH+Zs44AGXImcERU4cPBoKQ+9t5KfPDePIyXlvHxzD/4vqwsNamv4VHXI+veAq61eRxEJKmH/IebsdUX85p0ctuw5zKjeZ/Grwe2Ijw37fyzVqnuLBrRKrMOU7HxGZLTwOo5I0AjbFfjeQyX88s3l3DBxIbHREbz58948fEW6ytsDZsaIjFQWf7ub9YX7vY4jEjTCssCn527josdnMXXpFm6/oBUf3dWXjLRGXscKa1d1SyEqwpiSne91FJGgEVYFXrj/CLe9tpifv7aExPhY/nVHH349WMOnaoLEurFc2K4J7yzJ14ArkdMUFvsFzjneXrKF33+wisMlZfxqUFvGZLbU8KkaJsuXyoxV2/lsTSGDNB9F5JRCvsDzdh3i/qk5zPl6B76zGvLnYZ11E4Ea6oKKAVdvZuepwEVOQ8gWeHm545V5m3j047UAPHx5R67vdRYRml9SY0VFRjCsewrj53yjAVcipyEk9xDWFx4g6/l5PPT+KnxpjZhxbyajzktTeQeBLF8KZeXHtrxE5ORCagVeUlbOuNnf8OTMr6kVE8n/De/C1d2ba35JEGmZGE9GWkPezM7j5/004ErkZEJmBZ67ZS9XPD2Xv368los6NGHm2H4M0+TAoJTlOzbgKlsDrkROKugL/EhJGX+ZvoYrnplL0YGjPPfT7vzjunNJrBvrdTSppEs6a8CVyOkI6gJftGkXQ5+cw7NfbODqbs2ZeW8/Bqdr+FSwqx0TxWVdmvHhCg24EjmZoCzwA0dL+d2/chn+3DyKy8p59ZYe/HV4F+rXjvY6mvhJVkYqh0vK+GC5BlyJnMgpC9zMJppZoZnlfu+xv5rZGjNbYWZTzaxBYGP+xxdrCxn0+Gxenf8tN56Xxsf3ZNK3dWJ1HV6qSbfUBpzTJJ4p2dpGETmR01mBvwQMPu6xT4B051xnYB3wGz/n+oHdB4sZO2UZN764iLjoCN76eW8eurwjdTR8KiSZGSN8qSzZvEcDrkRO4JQF7pybDew67rEZzrnvNifnAykByPZv03O3MfDxWby3bCt3XngOH97Vl3PP0vCpUHdV9+YacCVyEv7YA78ZmHai3zSzMWaWbWbZRUVFlTrA2oIDJNevxXu/OJ//d3FbDZ8KEwnxsQxorwFXIidSpQI3sweAUmDSiZ7jnBvnnPM553yJiZXbq769fyum3n4eHZrVq2RSCVZZvlR2HCjm09WFXkcRqXEqXeBmNgq4FLjOOef8F+mHoiMjiNLkwLDUr00iTSoGXInIf6tUK5rZYOB/gMudc4f8G0nkP6IiIxh2bgqfry1k+74jXscRqVFO5zTC14F5QFszyzezW4CngbrAJ2a2zMyeC3BOCWNZvlTKHby9RB9minzfKc/Bc85d8yMPvxCALCI/6uyEOvQ4uxFvZudzW79Wmm8jUkEbyxIUsnypbNxxkEWbNOBK5DsqcAkKQzslER8bpQFXIt+jApegcGzAVTIf5Wxj/5ESr+OI1AgqcAkaWb6KAVcrtnkdRaRGUIFL0Oia2oDWGnAl8m8qcAkaZsaIjFSWbt7D19s14EpEBS5B5cpu3w240ipcRAUuQSUhPpaL2jflnSVbKC7VgCsJbypwCTpZGSnsPFjMZ2u2ex1FxFMqcAk6ma0TaVovVnPCJeypwCXoREVGMKx7Cl+sLaRgrwZcSfhSgUtQ0oArERW4BKm0hDr0PLsRb2bnEeBx9CI1lgpcglaWL5VNOw+xcOOuUz9ZJASpwCVoDe2UfGzAlc4JlzClApegVSsmksu6NNOAKwlbKnAJaiMyUjlSUs77yzXgSsKPClyCWpeU+rRpqgFXEp5U4BLUzIwsXyrL8vawTgOuJMyowCXoXdWtOdGRxhTdrUfCjApcgl7j7wZcLdWAKwkvKnAJCVm+VHZpwJWEGRW4hITMNokk1YvTTY8lrKjAJSRERhg/OTeFWeuKNOBKwsYpC9zMJppZoZnlfu+xRmb2iZl9XfG1YWBjipzacF+KBlxJWDmdFfhLwODjHrsP+NQ51xr4tOJ7EU+d1bgOvVo2Ykp2HuXlGnAloe+UBe6cmw0cPy3oCuDlil+/DFzp51wilZLlS+XbnYdYuEkDriT0VXYPvKlzbhtAxdcmJ3qimY0xs2wzyy4qKqrk4UROz5D0ZOrGRumccAkLAf8Q0zk3zjnnc875EhMTA304CXO1YiK5rGszPsrdxj4NuJIQV9kC325myQAVXwv9F0mkakb4vhtwtdXrKCIBVdkCfw8YVfHrUcC//BNHpOo6p9SnbdO6uumxhLzTOY3wdWAe0NbM8s3sFuDPwEAz+xoYWPG9SI1gZmRlpLI8bw9rCzTgSkLX6ZyFco1zLtk5F+2cS3HOveCc2+mcG+Cca13xVR/5S43y7wFXGjMrIUxXYkpIalQnhoEdmjJVA64khKnAJWR9N+Dq09UacCWhSQUuIatv60SS68fppscSslTgErK+G3A1e10R2/Ye9jqOiN+pwCWkDT839diAq8U6pVBCjwpcQlqLxrXp3bIxU7LzNeBKQo4KXEJeVkYKm3cdYsFGne0qoUUFLiFvSHoydeOidE64hBwVuIS8uOhILu/SjI9yNOBKQosKXMLCiIxUjpaW896y0B5wtfdQCbsPFnsdQ6pJlNcBRKpDp+b1aZdUlzez8/hpr7O8juNXRfuPMmNVAdNzC/hqw07q14rmtVt60qFZPa+jSYBpBS5hwczI8qWyPH8vawr2eR2nyrbtPcyLczeS9fw8ejwykwem5pK/+zCjzz+b2KgIrhk/n5z8vV7HlAAz56rv1Cqfz+eys7Or7Xgi37frYDE9H5nJ9b3S+N1lHbyOc8bydh1iWu42PsopYFneHgDaNI1ncHoyQzsl0bZpXcyMvF2HGDluPvuOlPDyzT3o3kL3HA92ZrbYOef7weMqcAknd0xawlcbdjD//gHERkV6HeeU1hceYHruNqblFrBy67GfHNKb12NIejKD05NolRj/o39uy57DXDt+PjsPFPPiTRlkpDWqztjiZycqcO2BS1jJykjlw5xtfLq6kKGdkr2O8wPOOdYU7GdazrHS/rrwAADdWjTggaHtGZyeRGqj2qd8neYNajF5TG+unTCfURMX8sKoDHq3ahzo+FLNtAKXsFJW7uj7l89o3bQuL9/cw+s4wLHSXpG/l2m5BUzP3camnYeIMMhIa8SQ9CQGpSeRXL9WpV67cP8Rrhu/gLzdhxh/g4++rXVf2mCkFbgI/xlw9dTn69m65zDNGlSuGKuqvNyxePNupuUU8PHKArbsOUxUhNG7VWPGZLbi4o5NSYiPrfJxmtSN440xvbhuwgJueTmb5396Lv3bNfHDO5CaQCtwCTubdx4i86+f8/8GtuHOAa2r7bilZeUs3Ljr2Ep7ZQFF+48SExlB39YJDOmUzEXtm9CgdkxAjr37YDHXT1zA2oL9PH1tdwZ1TArIcSQwtAIXqdCicW3Oa9WYKYvzuKP/OUREWMCOVVxaztwNO5ieU8Anq7ez62AxcdER9G/bhMHpSVzYrgl146IDdvzvNKwTw6TRvRg1cSF3TFrCkyO7cUnnmvcZgJwZFbiEpSxfKvdMXsb8jTs5r1WCX1/7SEkZs9cVMS23gJmrt7P/SCnxsVEMaN+EIelJ9GvThFox1X8GTP1a0bx6Sw9ufmkRd76+hNLyrlzRtXm15xD/UYFLWBqcnkTdf0UxZVGeXwr84NFSPl9byLTcAj5fU8ih4jLq14pmUMckhqQncX7rhBpx2mLduGheuqkHo1/O5p7JyyguLWe4L9XrWFJJKnAJS3HRkVzRtRlvZufz8OES6tc6822MvYdL+HT1dqblFjB7XRFHS8tJiI/hym7NGZKeRK+WjYmOrHkXO9eJjWLijRmMeTWbX721gpIyx7U9W3gdSypBBS5ha4SvBa/N38x7y7dy/WnOR9l1sJhPVhUwLbeAuet3UFLmSKoXxzU9WjA4PYmMtEZEBnBP3V9qxUQy/gYft722mPun5lBSVs6o89K8jiVnSAUuYSu9eb1/D7g6WYEX7jvCxyuPlfaCjbsoK3ekNqrFTX3OZnB6El1TGgT0g9BAiYuO5Lnrz+UX/1zKg++tpKSsnNF9W3odS85AlQrczO4FRgMOyAFucs4d8UcwkUAzM0ZkpPLw+6tYvW0f7ZP/M71vy57DTM8tYFrONhZv3o1z0CqxDrf1a8Xg9CQ6NquHWfCV9vFioyL5x3XdueeNZfzhw9UcLS3njv7neB1LTlOlC9zMmgN3AR2cc4fNbAowEnjJT9lEAu7Krs3500drmJKdx6jeaf++GnJ5xSS/dkl1uWdAG4Z2SqJ107oepw2M6MgInhzZlahI468fr6WkrJy7B7QOib+gQl1Vt1CigFpmVgLUBkJ7Wr6EnIZ1YhjYsSkvf7WJF+duAqBLSn3+Z3A7hqQnkZZQx9uA1SQqMoLHsroSHRnBEzO/pqSsnF9e3FYlXsNVusCdc1vM7G/AZuAwMMM5N+P455nZGGAMQIsW+qRbap7bL2jFkeIyerdqzOD0JFIannpYVCiKjDAeHdaZ6MgInvl8A8Wl5dw/tL1KvAar9KX0ZtYQeBsYAewB3gTecs69dqI/o0vpRWo+5xwPvbeSl+d9y43npfHgZR1U4h4LxKX0FwEbnXNFFQd4BzgPOGGBi0jNZ2Y8dHlHYqIiGD9nI0dLy/njlelBeaZNqKtKgW8GeplZbY5toQwAtLwWCQFmxv1D2xMdGcE/vthASVk5fxnWOSjOcQ8nVdkDX2BmbwFLgFJgKTDOX8FExFtmxq8GtSUm6tgHm6Vl5fxteBeiauDVpeGqSmehOOceBB70UxYRqWHMjHsuakN0ZETFKYaOJ0Z2rZEjAsKRrsQUkVO6o/85xEZF8IcPV1NSVs5T13arEcO5wp3+GhWR0zK6b0sevrwjM1Zt5+evLuZISZnXkcKeClxETtuo89J45KpOfL62iFtfyeZwsUrcSypwETkj1/ZswaM/6cyX63dw80uLOFRc6nWksKUCF5EzluVL5fGsrizYuJNRExey/0iJ15HCkgpcRCrlym7Neeqa7izdvIfrX1jI3sMq8eqmAheRSrukczLPXNedlVv38tMJC9hzqNjrSGFFBS4iVTKoYxLPX38ua7fv55rxC9h54KjXkcKGClxEquzCdk2ZcIOPb4oOcM34+RTu131dqoMKXET8IrNNIi/elEHersOMHDefgr0q8UBTgYuI35zXKoFXbulB4b6jjBg3jy17DnsdKaSpwEXErzLSGvHKLT3YdbCYEc/PI2/XIa8jhSwVuIj4XfcWDfnn6F7sP1LKiOfnsWnHQa8jhSQVuIgERKeU+rx+ay+OlJaT9fw81hce8DpSyFGBi0jAdGhWjzfG9KLcwchx81hbsN/rSCFFBS4iAdWmaV0m/6wXkRHGNePns2rrPq8jhQwVuIgEXKvEeCaP6U1cVATXjJ/Pivw9XkcKCSpwEakWaQl1mPyz3tSNi+K68QtYsnm315GCngpcRKpNaqPaTPlZbxrHx3D9hAUs3LjL60hBTQUuItWqWYNaTP5Zb5LqxzFq4kK+2rDD60hBSwUuItWuab043hjTm9RGtbjpxUXMXlfkdaSgpAIXEU8k1o3l9Vt70TIxntEvZ/PZmu1eRwo6KnAR8Uzj+Fhev7Un7ZLr8rNXFzM9t8DrSEFFBS4inmpQO4bXRvckvXl97vjnEj5YsdXrSEGjSgVuZg3M7C0zW2Nmq82st7+CiUj4qBcXzau39KR7iwbc9fpS3l26xetIQaGqK/AngenOuXZAF2B11SOJSDiKj43i5Zt70PPsxtw7ZRlTsvO8jlTjVbrAzawekAm8AOCcK3bO6fIqEam02jFRTLwxg/PPSeDXb63gqU+/pqSs3OtYNVZVVuAtgSLgRTNbamYTzKzO8U8yszFmlm1m2UVFOlVIRE6uVkwk42/wcVmXZvzfJ+u48pm55G7Z63WsGqkqBR4FdAeedc51Aw4C9x3/JOfcOOeczznnS0xMrMLhRCRcxEVH8tQ13Xjup93Zvu8oVzwzl0enr+FISZnX0WqUqhR4PpDvnFtQ8f1bHCt0ERG/GJyezKdj+3F1t+b844sNDP37HLI36fL771S6wJ1zBUCembWteGgAsMovqUREKtSvHc1fh3fhlZt7cLSknOHPz+PBf+Vy4Gip19E8V9WzUO4EJpnZCqAr8EjVI4mI/FBmm0Rm3JvJqN5pvDL/WwY9PptZYX4Jvjnnqu1gPp/PZWdnV9vxRCQ0Lf52F79+awUbig5ydffm/O7SDjSoHeN1rIAxs8XOOd/xj+tKTBEJOuee1YgP7+rLL/qfw3vLtnLRY7P4KGeb17GqnQpcRIJSXHQkvxzUln/9og9J9eO4fdISfv7qYgr3HfE6WrVRgYtIUOvYrD7v3t6H/xncjs/WFnLRY7OYkp1HdW4Pe0UFLiJBLyoygtsuaMX0u/vSLqkev35rBde/sJC8XYe8jhZQKnARCRktE+N5Y0wvfn9lOks37+bix2fz4tyNlJWH5mpcBS4iISUiwri+11nMGNuPni0b8fD7qxj+3FesL9zvdTS/U4GLSEhq3qAWL96YweMjuvDNjoMMffJLnv4stIZjqcBFJGSZGVd1S2Hm2H4M7NiUv81Yx2VPfUlOfmgMx1KBi0jIS4iP5Zlru/P89eey62AxVzzzJX+atjroh2OpwEUkbAzqmMQnY/uR5Uvl+VnfMOTJOSz4ZqfXsSpNBS4iYaV+rWj+PKwzk0b3pLS8nBHj5vPbd3PYf6TE62hnTAUuImGpzzkJfHxPJrecfzaTFmzm4sdn8/maQq9jnREVuIiErdoxUfzvpR14+7bziI+N4qaXFnHPG0vZdbDY62inRQUuImGve4uGfHDX+dw9oDUfrNjGwMdm8f7yrTX+cnwVuIgIEBsVyb0D2/DBXefTvGEt7nx9Kbe+spjtNXg4lgpcROR72iXV453bzuOBoe2Z83URFz02izcWbq6Rq3EVuIjIcaIiI7g1syUf35NJx2b1uO+dHK6bsIBvdx70Otp/UYGLiJxAWkId/jm6F49c1Ymc/L0MemI2E+Z8U2OGY6nARUROIiLCuLZnC2aMzaRPqwT+8OFqrn72K9YWeD8cSwUuInIakuvXYsIoH0+O7ErerkNc+tQcnpi5juJS74ZjqcBFRE6TmXFF1+Z8cm8mQzsl88TMr5Uc5KIAAATzSURBVLnsqS9ZnrfHkzwqcBGRM9Q4PpYnR3bjhVE+9h4u4ap/zOWPH67icHH1DsdSgYuIVNKA9k2ZMTaTkT1aMH7ORgY9MZuvNuyotuOrwEVEqqBeXDSPXNWJ12/thRlcO34Bv3knh33VMByrygVuZpFmttTMPvBHIBGRYNS7VWOm353JmMyWTF60mYGPzWLmqu0BPaY/VuB3A6v98DoiIkGtVkwk9w9tz9Tb+9CwdgyjX8nmrteXsvPA0YAcr0oFbmYpwCXABP/EEREJfl1SG/DeL85n7MA2TMvdxkWPzWLeBv/fOKKqK/AngF8DJzwR0szGmFm2mWUXFRVV8XAiIsEhJiqCuwa05sO7+pLevD5pCbX9foxKF7iZXQoUOucWn+x5zrlxzjmfc86XmJhY2cOJiASlNk3r8uotPUmuX8vvr12VFXgf4HIz2wS8AVxoZq/5JZWIiJxSpQvcOfcb51yKcy4NGAl85pz7qd+SiYjISek8cBGRIBXljxdxzn0BfOGP1xIRkdOjFbiISJBSgYuIBCkVuIhIkFKBi4gEKavOOy2bWRHwbSX/eAJQfXMaA0vvpeYJlfcBei81VVXey1nOuR9cCVmtBV4VZpbtnPN5ncMf9F5qnlB5H6D3UlMF4r1oC0VEJEipwEVEglQwFfg4rwP4kd5LzRMq7wP0Xmoqv7+XoNkDFxGR/xZMK3AREfkeFbiISJAKigI3s8FmttbM1pvZfV7nqSwzm2hmhWaW63WWqjCzVDP73MxWm9lKM7vb60yVZWZxZrbQzJZXvJeHvc5UFaFyk3Ez22RmOWa2zMyyvc5TFWbWwMzeMrM1Ff/N9Pbba9f0PXAziwTWAQOBfGARcI1zbpWnwSrBzDKBA8Arzrl0r/NUlpklA8nOuSVmVhdYDFwZpP+fGFDHOXfAzKKBL4G7nXPzPY5WKWY2FvAB9Zxzl3qdp7IqbhTjc84F/UU8ZvYyMMc5N8HMYoDazrk9/njtYFiB9wDWO+e+cc4Vc+zuP1d4nKlSnHOzgV1e56gq59w259ySil/vB1YDzb1NVTnumAMV30ZX/K9mr2pOQDcZr3nMrB6QCbwA4Jwr9ld5Q3AUeHMg73vf5xOkZRGKzCwN6AYs8DZJ5VVsOywDCoFPnHPB+l5OeZPxIOKAGWa22MzGeB2mCloCRcCLFVtbE8ysjr9ePBgK3H7ksaBcIYUaM4sH3gbucc7t8zpPZTnnypxzXYEUoIeZBd321uneZDyI9HHOdQeGAHdUbD8GoyigO/Csc64bcBDw2+d4wVDg+UDq975PAbZ6lEUqVOwXvw1Mcs6943Uef6j40fYLYLDHUSojpG4y7pzbWvG1EJjKsa3UYJQP5H/vp7q3OFbofhEMBb4IaG1mZ1d8ADASeM/jTGGt4oO/F4DVzrnHvM5TFWaWaGYNKn5dC7gIWONtqjMXSjcZN7M6FR+OU7HdcDEQlGduOecKgDwza1vx0ADAbx/2++WemIHknCs1s18AHwORwETn3EqPY1WKmb0OXAAkmFk+8KBz7gVvU1VKH+B6IKdi7xjgfufcRx5mqqxk4OWKs50igCnOuaA+BS8ENAWmHlsnEAX80zk33dtIVXInMKliAfoNcJO/XrjGn0YoIiI/Lhi2UERE5EeowEVEgpQKXEQkSKnARUSClApcRCRIqcBFRIKUClxEJEj9f5lZKRF6l01mAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "datastring = \"12 14 16 8 9 6 4\"\n",
    "datalist = datastring.split()\n",
    "print(datalist)\n",
    "intlist = []\n",
    "for x in datalist:\n",
    "    intlist.append(int(x))\n",
    "\n",
    "print(intlist)\n",
    "\n",
    "import matplotlib.pyplot as plt \n",
    "\n",
    "plt.plot(intlist)\n",
    "plt.show()\n"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "0ba00dd77806596ecbc07d55b4ddf41b2ae8cecbf91d9534027e74a33368b668"
  },
  "kernelspec": {
   "display_name": "Python 3.8.3 64-bit ('base': conda)",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
